#include <cstdlib>
#include <iostream>
#include <cmath>
#include <vector>
#include <sstream>
#include <fstream>

using namespace std;

int newton(int n, int k);

// Wyjątki:

class Exception {
public:
    string message;
};

class NaNException: public Exception {
public:
    string message;
    NaNException(string message):
    message(message){}
};

class FileNotFoundException: public Exception {
public:
    string message;
    FileNotFoundException(string message):
    message(message){}
};

class WrongDataFormatException: public Exception {
public:
    string message;
    WrongDataFormatException(string message):
    message(message){}
};

class WrongValueException: public Exception {
public:
    string message;
    WrongValueException(string message):
    message(message){}
};

class DataNotFoundException: public Exception {
public:
    string message;
    DataNotFoundException(string message):
    message(message){}
};

// Klasa przechowująca informację o odległościach między miastami
// oraz o poziomie feromonu (patrz -> opis działania algorytmu AntColony).
class Map {
private:
    vector<vector<double> > matrix;
    
public:
    
    // Konstruktor generujący losową mapę.
    Map(int size){
        assert(size > 0);
        matrix = vector<vector<double> >(size,size);
        for(int i = 0; i < size; i++){
            for(int j = 0; j < i; j++){
                setDistance(i, j, 1+(rand()%100));
                setPheromone(i, j, 1);
            }
            matrix[i][i] = 0;
        }
    }
    
    //TODO Konstruktor generujący mapę z pliku wejściowego.
    Map(char* file, int size){
        assert(size > 0);
        matrix = vector<vector<double> >(size,size);
        ifstream fs;
        fs.open(file);
        if(!fs.is_open()){
            throw FileNotFoundException("Nie znaleziono pliku wejsciowego!");
        }
        string line;
        getline(fs, line);
        int x, y;
        y = 1;
        while(fs){
            if(y == size){
                fs.close();
                throw WrongDataFormatException("Dane w pliku sa nieprawidlowe!");
            }
            x = 0;
            stringstream ss(line);
            string word;
            getline(ss, word, ' ');
            while(ss){
                int number;
                stringstream ss2(word);
                if(ss2 >> number && (x < y)){
                    setDistance(y, x, number);
                    setPheromone(y, x, 1);
                } else {
                    fs.close();
                    throw WrongDataFormatException("Dane w pliku sa nieprawidlowe!");
                }
                getline(ss, word, ' ');
                x++;
            }
            getline(fs, line);
            if(x != y){
                fs.close();
                throw WrongDataFormatException("Dane w pliku sa nieprawidlowe!");
            }
            y++;
        }
        if(y != size){
            fs.close();
            throw WrongDataFormatException("Dane w pliku sa nieprawidlowe!");
        }
        fs.close();
        
    }
    
    double getDistance(int i, int j){
        assert(i != j && !(i < 0 || j < 0) && i < getSize() && j < getSize());
        if(i > j) return matrix[i][j];
        else return matrix[j][i];
    }
    
    double getPheromone(int i, int j){
        assert(i != j && !(i < 0 || j < 0));
        if(i > j) return matrix[j][i];
        else return matrix[i][j];
    }
    
    int getSize(){
        return matrix.size();
    }
    
    void setDistance(int i, int j, double dist){
        assert(i != j && !(i < 0 || j < 0) && dist > 0);
        if(i > j) matrix[i][j] = dist;
        else matrix[j][i] = dist;
    }
    
    void setPheromone(int i, int j, double pherom){
        assert(i != j && !(i < 0 || j < 0) && pherom >= 0);
        if(i > j) matrix[j][i] = pherom;
        else matrix[i][j] = pherom;
    }
    
    void printMap(){
        cout << "Distances:";
        for(int i = 0; i < getSize(); i++){
            for(int j = 0; j < i; j++)
                cout << getDistance(i, j) << "\t";
            cout << endl;
        }
    }
    
    void printSolution(){
        
        cout << "Rozwiazanie: ";
        
        vector<bool> unvisitedNodes = vector<bool>(getSize(), true);
        
        int currentNode = 0;
        unvisitedNodes[0] = false;
        cout << "0";
        
        for(int i = 0; i < getSize(); i++){
            double greatestPherom = 0;
            int greatestPheromIndex = 0;
            for(int j = 0; j < getSize(); j++){
                if(i != j && unvisitedNodes[j] && greatestPherom < getPheromone(i, j)){
                    greatestPherom = getPheromone(i, j);
                    greatestPheromIndex = j;
                }
            }
            unvisitedNodes[greatestPheromIndex] = false;
            cout << " -> " << greatestPheromIndex;
        }
    }
    
    //Metoda do debugowania.
    void printit(){
        for(int i = 0; i < getSize(); i++){
            for(int j = 0; j < getSize(); j++)
                cout << matrix[i][j] << "\t";
            cout << endl;
        }
    }
    
};

//Klasa mrowki - jednorazowo (w konstruktorze) wyznacza trase i przechowuje ja.
class Ant {
protected:
    Map* map;
    vector<vector<int> > track;
    vector<int> unvisitedNodes;
    void visit(int node){
        //TODO Wyjątek dla pustego unvisitedNodes (null) i dla zlego parametru
        vector<int>::iterator it;
        for(it = unvisitedNodes.begin(); it != unvisitedNodes.end(); ++it){
            if(*it == node){
                unvisitedNodes.erase(it);
                break;
            }
        }
    }
    
    //Dwie pomocnicze metody do obliczania prawdopodobienstwa wybrania danej sciezki.    
    double pheromoneFactor(int x, int y){
        double a = 0.5; //Wpływ pozostawionego feromonu na wybór trasy
        return 1.0*pow(map->getPheromone(x, y), a);
    }
    
    double distanceFactor(int x, int y){
        double b = 0.5; //Wpływ odległości między miastami na wybór trasy
        return 1.0*pow((1.0/map->getDistance(x, y)), b);
    }
    
public:
    
    Ant(Map *m):map(m){
        
        //Wypełnienie zbioru nieodwiedzonych miast
        unvisitedNodes = vector<int>(m->getSize(), 0); 
        for(int i = 0; i < m->getSize(); i++)
            unvisitedNodes[i] = i;
        
        //Losowanie startowego miasta
        int currentNode = 0; //TODO Stworzyć losowanie startowego miasta
        visit(currentNode);
        
        //Przygotowywanie ostatniego kroku (ostatnie miasto -> miasto poczatkowe)
        vector<int> lastStep = vector<int>(2,0);
        lastStep[1] = currentNode;
        
        //Obliczenia dla wszystkich krokow
        while(unvisitedNodes.size() > 0){
            
            //Przygotowanie kroku
            vector<int> step = vector<int>(2,0);
            step[0] = currentNode;
            
            //Obliczanie wstepne prawdopodobienstwa dla poszczegolnych krokow
            vector<double> probabilities = vector<double>(unvisitedNodes.size(),0);
            
            for(int i = 0; i < unvisitedNodes.size(); i++)
                probabilities[i] = 1.0*pheromoneFactor(currentNode, unvisitedNodes[i])*distanceFactor(currentNode, unvisitedNodes[i]);
            
            //Obliczanie mianownika dla obecnego zbioru nieodwiedzonych miast
            double denominator = 0.0;
            for(int i = 0; i < unvisitedNodes.size(); i++)
                denominator += probabilities[i];
            
            //Zakończenie obliczen prawdopodobienstw
            for(int i = 0; i < unvisitedNodes.size(); i++)
                probabilities[i] = probabilities[i]/denominator;
            
            //Losowanie
            double randomNumber = 1.0*rand()/RAND_MAX;
            
            assert(randomNumber >= 0 && randomNumber <= 1);
            
            //Okreslanie wylosowanej sciezki
            for(int i = 0; i < probabilities.size(); i++){
                randomNumber -= probabilities[i];
                //Umieszczenie tej podmiany tutaj a nie w ifie zapobiega niewybraniu zadnej sciezki (np. w razie bledu w dzieleniu)
                currentNode = unvisitedNodes[i]; 
                if(randomNumber <= 0){
                    break;
                }
            }
            
            //Wykonywanie kroku
            visit(currentNode);
            step[1] = currentNode;
            track.push_back(step);
        }
        
        //Wykonywanie ostatniego kroku
        lastStep[0] = currentNode;
        track.push_back(lastStep);
        
    }
    
    vector<vector<int> > getTrack(){
        return track;
    }
    
    double trackLength(){
        double length = 0;
        for(int i = 0; i < track.size(); i++)
            length += map->getDistance(track[i][0], track[i][1]);
        return length;
    }
    
};

class AntColony {
private:
    bool mapFlag;
    Map* map;
    
public:
    
    AntColony(){
        mapFlag = false;
    }
    
    AntColony(int size){
        assert(size > 0);
        mapFlag = false;
        setMap(size);
    }
    
    AntColony(Map *m){
        mapFlag = false;
        setMap(m);
    }
    
    void setMap(int size){
        map = new Map(size);
        mapFlag = true;
    }
    
    void setMap(Map *m){
        map = m;
        mapFlag = true;
    }
    
    void run(int numberOfAnts, int numberOfIterations){
        assert(mapFlag);
        
        //Przejscie algorytmu
        for(int i = 0; i < numberOfIterations; i++){
            //Tworzenie i wypuszczanie mrowek
            vector<Ant*> ants = vector<Ant*>(numberOfAnts);
            for(int j = 0; j < numberOfAnts; j++)
                ants[j] = new Ant(map);
            
            //Odparowanie czesci feromonu
            for(int x = 0; x < map->getSize(); x++)
                for(int y = 0; y < x; y++){
                    double p = 0.5;     //Wspolczynnik odparowania feromonu
                    //Obliczenie i zapisanie nowego stezenia feromonu
                    double newPheromLevel = 1.0 * map->getPheromone(x, y)*(1.0-p);     
                    map->setPheromone(x, y, newPheromLevel);
                }
            
            //Umieszczenie feromonu na trasach mrowek
            for(int j = 0; j < numberOfAnts; j++){
                for(int k = 0; k < map->getSize(); k++){
                    //Obliczenie i zapisanie nowego stezenia feromonu
                    int x = ants[j]->getTrack()[k][0];
                    int y = ants[j]->getTrack()[k][1];
                    double newPheromLevel = map->getPheromone(x, y) + (1.0/ants[j]->trackLength());
                    map->setPheromone(x, y, newPheromLevel);
                }
            }
            
            //Zwalnianie pamieci po mrowkach (w koncu to C++ ;/)
            for(int j = 0; j < numberOfAnts; j++)
                delete ants[j];
                    
        }
        
    }
    
    void printMap() {
        if(!mapFlag)
            throw DataNotFoundException("Najpierw wczytaj dane!");
        map->printMap();
    }
    
    void printSolution() {
        if(!mapFlag)
            throw DataNotFoundException("Najpierw wczytaj dane!");
        map->printSolution();
    }
    
    //Metoda do debugowania.
    void printit() {
        map->printit();
    }
    
};

int getInt(){
    string input = "";
    int number = 0;
    getline(cin, input);
    stringstream myStream(input);
    if (myStream >> number)
        return number;
    throw NaNException("Wartosc nie jest numerem!");
}



int getNumber(int a, int b){
    int number = getInt();
    if(number >= a && number <= b)
        return number;
    throw WrongValueException("Liczba musi miescic sie w zadanym przedziale!");
}

int factorial(int x) {
    return (x == 1 ? x : x * factorial(x - 1));
}

int newton(int n, int k) {
    return factorial(n) / ( factorial(k) * factorial(n-k) );
}

int main(int argc, char** argv) {
    
    try{
    
        cout << endl << "#####################################################################";
        cout << endl << "#####################################################################";
        cout << endl << "##                                                                 ##";
        cout << endl << "## Solving a Travelling Salesman Problem with Ant Colony Algorithm ##";
        cout << endl << "##                                                                 ##";
        cout << endl << "#####################################################################";
        cout << endl << "#####################################################################";
        cout << endl << "##                                                                 ##";
        cout << endl << "##          Authors: Pawel Mlynarczyk & Piotr Romanski             ##";
        cout << endl << "##                                                                 ##";
        cout << endl << "#####################################################################";
        cout << endl << "#####################################################################";
        cout << endl;
        cout << endl;


        bool exitFlag = true;
        bool keyFlag = true;
        char state = '0';

        AntColony* antColony = NULL;
        bool dataFlag = false;

        while(exitFlag){
            switch(state){
                case 1:
                    cout << endl << "Wczytuje dane z pliku 'data.txt'...";
                    if(dataFlag)
                        delete [] antColony;
                    dataFlag = false;

                    int citiesf;
                    citiesf = -1;
                    while(citiesf < 0){
                        try{
                            cout << endl << "Podaj rozmiar (ilosc miast) danych w pliku";
                            cout << endl << "(rozmiar musi zawierac sie z przedziale 2-100): ";
                            citiesf = getNumber(2, 100);
                        } catch (WrongValueException e) {
                            cout << e.message;
                            citiesf = -1;
                        } catch (NaNException e) {
                            cout << e.message;
                            citiesf = -1;
                        }
                    }

                    try{
                        antColony = new AntColony(new Map("data.txt", citiesf));
                        dataFlag = true;
                        cout << "Wczytano mape!" << endl;
                    } catch(FileNotFoundException e){
                        cout << e.message;
                    } catch(WrongDataFormatException e){
                        cout << e.message;
                    }

                    keyFlag = false;
                    state = '0';
                    break;

                case 2:

                    int cities;
                    cities = -1;
                    while(cities < 0){
                        try{
                            cout << endl << "Ile miast chcesz odwiedzic? [2-100] ";
                            cities = getNumber(2, 100);
                        } catch (WrongValueException e) {
                            cout << e.message;
                            cities = -1;
                        } catch (NaNException e) {
                            cout << e.message;
                            cities = -1;
                        }
                    }

                    if(dataFlag)
                        delete [] antColony;

                    antColony = new AntColony(cities);
                    dataFlag = true;

                    cout << "Wczytano mape!" << endl;

                    keyFlag = false;
                    state = '0';
                    break;

                case 3:
                    if(dataFlag)
                        try{
                            antColony->printMap();
                        } catch(DataNotFoundException e) {
                            cout << e.message;
                        }
                    else{
                        cout << "Najpierw wczytaj dane!";
                    }

                    keyFlag = false;
                    state = '0';
                    break;
                case 4:

                    if(!dataFlag){
                        cout << "Najpierw wczytaj/wygeneruj dane!";
                        keyFlag = false;
                        state = '0';
                        break;
                    }

                    int ants;
                    ants = -1;
                    while(ants < 0){
                        try{
                            cout << endl << "Ile mrowek chcesz wykorzystac? [1-500] "; 
                            ants = getNumber(1, 500);
                        } catch (WrongValueException e) {
                            cout << e.message;
                            ants = -1;
                        } catch (NaNException e) {
                            cout << e.message;
                            ants = -1;
                        }
                    }

                    int iters;
                    iters = -1;
                    while(iters < 0){
                        try{
                            cout << endl << "Ile iteracji algorytmu chcesz wykonac? [1-500] ";
                            iters = getNumber(1, 500);
                        } catch (WrongValueException e) {
                            cout << e.message;
                            iters = -1;
                        } catch (NaNException e) {
                            cout << e.message;
                            iters = -1;
                        }
                    }

                    antColony->run(ants, iters);
                    cout << endl << "Wykonano algorytm!" << endl;
                    antColony->printSolution();

                    keyFlag = false;
                    state = '0';
                    break;
                case 5:
                    exitFlag = false;
                    keyFlag = false;
                    break;
                default:
                    cout << endl << "Menu:";
                    cout << endl << "1. Wczytaj dane z pliku.";
                    cout << endl << "2. Wczytaj losowe dane.";
                    cout << endl << "3. Wypisz dane.";
                    cout << endl << "4. Wykonaj algorytm i wypisz wynik.";
                    cout << endl << "5. Wyjdz z programu.";
                    cout << endl << "Twoj wybor: ";
                    keyFlag = true;
                    state = '0';
                    break;
            }
            if(keyFlag){
                try{
                    state = getInt();
                } catch(NaNException e) {
                    cout << e.message << endl;
                    state = 0;
                }
            }
        }
        return 0;
    } catch(Exception e) {
        cout << endl << "Nieoczekiwany wyjatek, program zostanie zamkniety.";
        cout << endl << e.message;
        exit(0);
    }
    
    
}

